package string_question.leecode.test28;

/**
 * 方法二：KMP算法
 * 时间复杂度（m + n）  空间复杂度 next数组（n）
 * @author code_yc
 * @version 1.0
 * @date 2020/7/5 9:24
 */
public class Solution2 {

    public int strStr(String haystack, String needle) {
        // 1 边界条件判断
        if (haystack == null || needle == null || haystack.length() < needle.length()) return -1;
        if (needle.equals("")) return 0;

        // 2 将字符串转化为字符数组，并求出needle字符串的next数组
        char[] chh = haystack.toCharArray();
        char[] chn = needle.toCharArray();
        int[] next = getNextArr(chn);

        // 3 利用next数组进行求解
        int ch = 0, cn = 0;
        while (ch < chh.length && cn < chn.length) {
            if (chh[ch] == chn[cn]) {
                ch++;
                cn++;
            } else if (next[cn] == -1) {
                ch++;
            } else {
                cn = next[cn];
            }
        }

        // 4 返回结果集
        return cn == chn.length ? ch - cn : -1;
    }

    // 计算next数组
    private int[] getNextArr(char[] chn) {
        int len = chn.length;
        if (len == 1) return new int[]{-1};
        int[] next = new int[len];
        next[0] = -1;
        next[1] = 0;
        int cn = 0;
        int pos = 2;
        while (pos < len) {
            if (chn[pos - 1] == chn[cn]) {
                next[pos++] = ++cn;
            } else if (cn > 0) {
                cn = next[cn];
            } else {
                next[pos++] = 0;
            }
        }
        return next;
    }
}
